/*
 * @lc app=leetcode.cn id=21 lang=javascript
 *
 * [21] 合并两个有序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
/**
 * 定义虚拟头节点ret, 定义指针p3指向ret;
 * 定义p1、p2 分别指向l1、l2。
 * 遍历两条链表，值小的节点接在p3后面。
 * 如果其中一条链表遍历结束，则将另一条链表剩余部分接到p3后面。
 */
var mergeTwoLists = function(l1, l2) {
  if(!l1 || !l2) return l1 || l2;
  let p1 = l1, p2 = l2;
  let ret = new ListNode(null);
  let p3 = ret;
  while(p1 && p2) {
    if(p1.val < p2.val) {
      p3.next = p1;
      p1 = p1.next;
    } else {
      p3.next = p2;
      p2 = p2.next;
    } 
    p3 = p3.next;

    // 其中一条链表遍历结束，将另一条链表剩余部分接到p3后面。
    if(!p1 || !p2) {
      p3.next = p1 || p2;
    }
  }
  return ret.next;
};
// @lc code=end

